Day 28 Easy x 2

LeetCode 100 題

待優化的兩題

1. Guess Number Higher or Lower
2. Diameter of Binary Tree

LeetCode 374. Guess Number Higher or Lower

Source

https://leetcode.com/problems/guess-number-higher-or-lower/

use API-guess(n)

tags: 經典題

1.題意:

• In and Out
  In: n
  n代表 欲pick的輸入在1~n間(inclusive 1,n)

  def guessNumber(self, n: int) -> int:

  但是 Test case為兩個數字 n,pick

  Out: pick

• API說明

  會使用到guess(...)這個API
  參數為n，也就是內部程式會將pick 與 n 比大小

  pick 比 n 大，回傳-1
  pick 比 n 小，回傳1
  pick, n 兩者一樣則回傳0

• Notice: Brute Force 會超時

2.思路:

tags: 常用解

• Binary Search
  設定兩個指針 low, high
  初始為 low = 1, high= n
  先猜答案落在 mid 位置，也就是1與n的中間，

如果 mid 剛好 hit(命中) pick 則回傳 mid

如果pick比mid大，則代表pick落在右區間，
把 low 移到 mid 右邊，也就是 low = mid + 1，

如果pick比mid小，則代表pick落在左區間，
把 high 移到 mid 左邊，也就是 high = mid - 1，

PS: 因 1~n 為照序排好的情況，因此可做Binary Search

3.程式碼:

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:

        
        if guess(n)==0:
            return n
        low  = 1
        high = n
        
        while low<=high: # imp: = 
            print(low,high)
            mid = int((low+high)/2)
            print(mid)
            if guess(mid) == 0:
                return mid
                
            if guess(mid) == (-1):
                high = mid -1
            if guess(mid) == 1:
                low = mid+1
        #return -1        

Result:

• More info.(total solution):
  https://leetcode.com/problems/guess-number-higher-or-lower/solution/
• Next try optimize:
  • ★ Ternary Search or 其他更快的方法

LeetCode 543. Diameter of Binary Tree

Source

https://leetcode.com/problems/diameter-of-binary-tree/

不easy的easy

等我更了解後，再來記錄!